package com.fanshuai.algorithms.divide;

/**
 * 给定正整数n和m，利用分治算法计算出n个元素的结合{1,2,...,n}可以划分为多少个不通过的由m个非空子集组成的集合。
 */
public class CollectionDivide {
    /**
     * 动态规划解法：
     * dp[i][j] 表示将j个元素划分为i个非空集合的集合个数
     *
     * dp[i][j] = dp[i-1][j-1] + dp[i][j-1] * i
     *
     * dp[i-1][j-1]：将元素j划分为单独的集合，剩余的j-1个元素划分为i-1个集合
     * dp[i][j-1] * i: 将j-1个元素划分为i个集合，并且将元素j加入到m个集合其中的一个
     *
     * badcase: dp[1][j] = 1, dp[i][1] = 0(i>=2)
     * @param n
     * @param m
     * @return
     */
    public static int collectionDivide(int n, int m) {
        int[][] dp = new int[m + 1][n + 1];

        for (int j = 1; j <= n; j++) {
            dp[1][j] = 1;
        }
        for (int i = 2; i <= m; i++) {
            dp[i][1] = 0;
        }

        for (int i = 2; i <= m; i++) {
            for (int j = 2; j <= n; j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1] * i;
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(collectionDivide(7, 4));
    }
}
